/**
 * Created by zhourh on 2018/6/12.
 */
public class ToeplitzMatrix {

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1,2,3,4},{5,1,2,3},{9,5,1,2}};
        System.out.println(new ToeplitzMatrix().isToeplitzMatrix(matrix));

        matrix = new int[][]{{1,2}, {2,2}};
        System.out.println(new ToeplitzMatrix().isToeplitzMatrix(matrix));
    }

    public boolean isToeplitzMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }

        if (matrix.length == 1) {
            return true;
        }

        int width = matrix[0].length;
        int height = matrix.length;

        for (int row = height - 2, column = 0; row > 0 || column < width - 1;) {
            int value = matrix[row][column];
            int tRow = row;
            int tColumn = column;
            while (tRow + 1 < height && tColumn + 1 < width) {
                if (matrix[tRow + 1][tColumn + 1] != value) {
                    return false;
                }
                tRow++;
                tColumn++;
            }

            if (row - 1 >= 0 ) {
                row--;
                continue;
            }

            if (column + 1 < width) {
                column++;
                continue;
            }
        }

        return true;
    }
}
